"""P4 4. 详解桶排序以及排序内容大总结"""

import heapq

"""
完全二叉树：
i位置的左位置：2 * i + 1
i位置的右位置：2 * i + 2
i位置的父位置：(i - 1) // 2
特殊的完全二叉树是满二叉树

完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
完全二叉树中如果每棵子树的最小值都在顶部就是小根堆

优先级队列结构就是堆结构
"""


class HeapSort:

    def __init__(self, arr: list):
        """大根堆排序，时间复杂度O(N * log(2, N))，额外空间复杂度O(1)"""
        heap_size = len(arr)
        for i in range(heap_size):
            self.heap_insert(arr, i)
        # 快一点的大根堆初始化
        # for i in range(heap_size - 1, -1, -1):
        #     self.heapify(arr, i, heap_size)
        heap_size -= 1
        self.swap(arr, 0, heap_size)
        while heap_size > 0:
            self.heapify(arr, 0, heap_size)
            heap_size -= 1
            self.swap(arr, 0, heap_size)

    @staticmethod
    def heap_insert(arr: list, index: int):
        """index位置的数往上移动"""
        while arr[index] > arr[int((index - 1) / 2)]:
            HeapSort.swap(arr, index, (index - 1) // 2)
            index = (index - 1) // 2

    @staticmethod
    def heapify(arr: list, index: int, heap_size: int):
        """index位置的数往下移动"""
        left = index * 2 + 1
        while left < heap_size:
            # 两个孩子中较大值的下标赋给largest
            largest = left + 1 if (
                    left + 1 < heap_size and arr[left] < arr[left + 1]
            ) else left
            # 父和较大孩子比较，较大的将下标赋给largest
            largest = largest if arr[largest] > arr[index] else index
            # 孩子的值没父的大就下移结束
            if index == largest:
                break
            # 交换值
            HeapSort.swap(arr, largest, index)
            # 更新index、left
            index = largest
            left = index * 2 + 1

    @staticmethod
    def swap(arr: list, a: int, b: int):
        arr[a], arr[b] = arr[b], arr[a]


def sorted_arr_distance_less_k(arr: list, k: int):
    """将数组排序，每个元素移动距离不超过k"""
    # 使用python自带的heapq类实现最小堆操作
    heap = list()
    for i in range(min(len(arr), k)):
        heapq.heappush(heap, arr[i])
    i = 0
    for j in range(k, len(arr)):
        heapq.heappush(heap, arr[j])
        arr[i] = heapq.heappop(heap)
        i += 1
    while heap:
        arr[i] = heapq.heappop(heap)
        i += 1


"""
桶排序、基数排序、计数排序是不基于比较的排序，根据数据状况而定
"""


class RadixSort:

    def __init__(self, arr: list):
        """基数排序"""
        if not arr:
            return
        # 获取最大位数digit
        max_num = arr[0]
        for i in range(1, len(arr)):
            max_num = arr[i] if arr[i] > max_num else max_num
        digit = 0
        while max_num != 0:
            digit += 1
            max_num = max_num // 10
        # 从个位开始向左处理
        bucket = [0] * len(arr)
        for d in range(digit):
            count = [0] * 10
            # 遍历arr给count对于位赋值
            for i in arr:
                count[self.get_digit(i, d)] += 1
            # count累加赋值
            for i in range(1, 10):
                count[i] += count[i - 1]
            # 遍历arr，根据count填入bucket中
            for i in range(len(arr) - 1, -1, -1):
                j = self.get_digit(arr[i], d)
                bucket[count[j] - 1] = arr[i]
                count[j] -= 1
            for i in range(len(arr)):
                arr[i] = bucket[i]

    @staticmethod
    def get_digit(num: int, digit: int) -> int:
        """获取num数字的从右往左数第digit位的值"""
        return (num // (10 ** digit)) % 10


"""
稳定性指的是相同值的数在排序后相对位置不变

不具备稳定性的排序：
选择排序、快速排序、堆排序
具备稳定性的排序：
冒泡排序、插入排序、归并排序、计数排序、基数排序

稳定性用归并排序
时间少用快速排序
空间少用堆排序
"""


if __name__ == "__main__":
    array = [2, 4, 6, 13, 866, 4, 2]
    # HeapSort(array)
    # sorted_arr_distance_less_k(array, len(array))
    RadixSort(array)
    print(array)
